import { useMemo, useState } from 'react';
import { TreeNode, buildBSTFromArray, validateBST } from '@ds/tree';
import { Space, Input, Typography, Tag, Card, Alert } from 'antd';

function levelOrder(root: TreeNode | null): (number | null)[][] {
  const result: (number | null)[][] = [];
  if (!root) return result;
  const queue: (TreeNode | null)[] = [root];
  while (queue.length) {
    const size = queue.length;
    const level: (number | null)[] = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift() ?? null;
      if (node) {
        level.push(node.val);
        queue.push(node.left);
        queue.push(node.right);
      } else {
        level.push(null);
      }
    }
    // 避免尾部全是null的层级
    if (level.some((v) => v !== null)) {
      result.push(level);
    }
  }
  return result;
}

// 记录删除过程的辅助函数
function deleteWithTrace(
  root: TreeNode | null,
  key: number
): {
  root: TreeNode | null;
  steps: Array<{
    action: string;
    nodeVal?: number;
    description: string;
  }>;
} {
  const steps: Array<{
    action: string;
    nodeVal?: number;
    description: string;
  }> = [];

  // 先检查节点是否存在
  let nodeExists = false;
  function checkExistence(node: TreeNode | null): void {
    if (!node) return;
    if (node.val === key) {
      nodeExists = true;
    }
    if (!nodeExists) checkExistence(node.left);
    if (!nodeExists) checkExistence(node.right);
  }
  checkExistence(root);

  if (!nodeExists) {
    steps.push({
      action: 'NOT_FOUND',
      description: `未找到值为 ${key} 的节点`,
    });
    return { root, steps };
  }

  // 执行删除并记录步骤
  function deleteAndTrace(
    node: TreeNode | null,
    key: number,
    _parent?: TreeNode,
    _isLeft?: boolean
  ): TreeNode | null {
    if (!node) return null;

    steps.push({
      action: 'SEARCH',
      nodeVal: node.val,
      description: `当前节点值: ${node.val}, 搜索目标: ${key}`,
    });

    if (key < node.val) {
      steps.push({
        action: 'GO_LEFT',
        description: `${key} < ${node.val}, 前往左子树`,
      });
      node.left = deleteAndTrace(node.left, key, node, true);
    } else if (key > node.val) {
      steps.push({
        action: 'GO_RIGHT',
        description: `${key} > ${node.val}, 前往右子树`,
      });
      node.right = deleteAndTrace(node.right, key, node, false);
    } else {
      // 找到要删除的节点
      steps.push({
        action: 'FOUND',
        nodeVal: node.val,
        description: `找到要删除的节点: ${node.val}`,
      });

      // 情况1: 叶子节点
      if (!node.left && !node.right) {
        steps.push({
          action: 'DELETE_LEAF',
          nodeVal: node.val,
          description: `删除叶子节点 ${node.val}`,
        });
        return null;
      }

      // 情况2: 只有一个子节点
      else if (!node.left) {
        steps.push({
          action: 'DELETE_ONE_CHILD',
          nodeVal: node.val,
          description: `节点 ${node.val} 只有右子树，用右子树替代`,
        });
        return node.right;
      } else if (!node.right) {
        steps.push({
          action: 'DELETE_ONE_CHILD',
          nodeVal: node.val,
          description: `节点 ${node.val} 只有左子树，用左子树替代`,
        });
        return node.left;
      }

      // 情况3: 有两个子节点
      steps.push({
        action: 'DELETE_TWO_CHILDREN',
        nodeVal: node.val,
        description: `节点 ${node.val} 有两个子节点，寻找后继节点`,
      });

      // 找到右子树中的最小节点（后继）
      let successorParent = node;
      let successor = node.right;
      while (successor.left) {
        successorParent = successor;
        successor = successor.left;
      }

      steps.push({
        action: 'FIND_SUCCESSOR',
        nodeVal: successor.val,
        description: `找到后继节点: ${successor.val}`,
      });

      // 用后继节点的值替换当前节点的值
      steps.push({
        action: 'REPLACE_VALUE',
        description: `用后继节点 ${successor.val} 的值替换当前节点 ${node.val}`,
      });
      node.val = successor.val;

      // 删除后继节点
      steps.push({
        action: 'DELETE_SUCCESSOR',
        nodeVal: successor.val,
        description: `删除后继节点 ${successor.val}`,
      });

      if (successorParent === node) {
        successorParent.right = successor.right;
      } else {
        successorParent.left = successor.right;
      }
    }

    return node;
  }

  const newRoot = deleteAndTrace(root, key);
  steps.push({
    action: 'COMPLETE',
    description: '删除操作完成，保持二叉搜索树性质',
  });

  return { root: newRoot, steps };
}

export default function BSTDeleteNode() {
  const [input, setInput] = useState('5,3,7,2,4,6,8');
  const [deleteValue, setDeleteValue] = useState('3');
  const [currentRoot, setCurrentRoot] = useState<TreeNode | null>(null);
  const [deleteSteps, setDeleteSteps] = useState<
    Array<{
      action: string;
      nodeVal?: number;
      description: string;
    }>
  >([]);
  const [deletePerformed, setDeletePerformed] = useState(false);

  const values = useMemo(
    () =>
      input
        .split(/[\,\s]+/)
        .filter(Boolean)
        .map(Number)
        .filter((n) => Number.isFinite(n)),
    [input]
  );

  const initialRoot = useMemo(() => buildBSTFromArray(values), [values]);
  const valid = useMemo(() => validateBST(currentRoot || initialRoot), [currentRoot, initialRoot]);
  const deleteNum = useMemo(() => Number(deleteValue), [deleteValue]);
  const isDeleteValid = useMemo(() => Number.isFinite(deleteNum), [deleteNum]);

  const levels = useMemo(() => levelOrder(currentRoot || initialRoot), [currentRoot, initialRoot]);

  const handleDelete = () => {
    if (!isDeleteValid) return;

    const { root, steps } = deleteWithTrace(initialRoot, deleteNum);
    setCurrentRoot(root);
    setDeleteSteps(steps);
    setDeletePerformed(true);
  };

  const handleReset = () => {
    setCurrentRoot(null);
    setDeleteSteps([]);
    setDeletePerformed(false);
  };

  return (
    <Space direction="vertical" size="middle" style={{ width: '100%' }}>
      <Typography.Title level={2}>450. 删除二叉搜索树中的节点</Typography.Title>

      <Alert
        message="LeetCode 450. 删除二叉搜索树中的节点"
        description={
          <Typography.Paragraph style={{ marginBottom: 0 }}>
            给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，
            并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
            <Typography.Link
              href="https://leetcode.cn/problems/delete-node-in-a-bst/"
              target="_blank"
              style={{ marginLeft: 8 }}
            >
              题目链接
            </Typography.Link>
          </Typography.Paragraph>
        }
        type="info"
        showIcon
      />

      <Space>
        <Input
          allowClear
          value={input}
          onChange={(e) => setInput(e.target.value)}
          placeholder="例如: 5,3,7,2,4,6,8"
          style={{ width: 320 }}
        />
        <Input
          allowClear
          value={deleteValue}
          onChange={(e) => setDeleteValue(e.target.value)}
          placeholder="要删除的值，例如: 3"
          style={{ width: 160 }}
        />
        <Space>
          <button
            onClick={handleDelete}
            disabled={!isDeleteValid}
            style={{
              padding: '4px 15px',
              backgroundColor: isDeleteValid ? '#1890ff' : '#d9d9d9',
              color: 'white',
              border: 'none',
              borderRadius: '4px',
              cursor: isDeleteValid ? 'pointer' : 'not-allowed',
            }}
          >
            删除节点
          </button>
          <button
            onClick={handleReset}
            style={{
              padding: '4px 15px',
              backgroundColor: '#52c41a',
              color: 'white',
              border: 'none',
              borderRadius: '4px',
              cursor: 'pointer',
            }}
          >
            重置
          </button>
        </Space>
      </Space>

      <Space wrap>
        <Alert
          message={`是否有效BST：${String(valid)}`}
          type={valid ? 'success' : 'error'}
          showIcon
        />
        {deletePerformed && (
          <Alert
            message={`删除操作${deleteSteps.some((step) => step.action === 'NOT_FOUND') ? '：未找到节点' : '完成'}`}
            type={deleteSteps.some((step) => step.action === 'NOT_FOUND') ? 'warning' : 'success'}
            showIcon
          />
        )}
      </Space>

      {deleteSteps.length > 0 && (
        <Card title="删除操作步骤" size="small">
          <div style={{ maxHeight: 300, overflowY: 'auto', display: 'grid', rowGap: 6 }}>
            {deleteSteps.map((step, index) => (
              <div
                key={index}
                style={{
                  display: 'flex',
                  alignItems: 'center',
                  gap: 8,
                  padding: '4px 8px',
                  backgroundColor:
                    step.action === 'FOUND' ||
                    step.action === 'DELETE_LEAF' ||
                    step.action === 'DELETE_ONE_CHILD' ||
                    step.action === 'DELETE_TWO_CHILDREN'
                      ? '#e6f7ff'
                      : 'transparent',
                }}
              >
                <Tag
                  color={
                    step.action === 'NOT_FOUND'
                      ? 'red'
                      : step.action === 'FOUND'
                        ? 'orange'
                        : step.action.startsWith('DELETE')
                          ? 'green'
                          : 'blue'
                  }
                >
                  {index + 1}
                </Tag>
                <Typography.Text>
                  {step.description}
                  {step.nodeVal !== undefined && (
                    <Typography.Text code style={{ marginLeft: 4 }}>
                      {step.nodeVal}
                    </Typography.Text>
                  )}
                </Typography.Text>
              </div>
            ))}
          </div>
        </Card>
      )}

      <Card title={deletePerformed ? '删除后的树' : '原始树'}>
        {levels.length === 0 ? (
          <em>空树</em>
        ) : (
          <div style={{ display: 'grid', gap: 8 }}>
            {levels.map((level, idx) => (
              <div key={idx} style={{ display: 'flex', justifyContent: 'center', gap: 6 }}>
                {level.map((val, i) => (
                  <div
                    key={i}
                    style={{
                      minWidth: 36,
                      minHeight: 36,
                      border: '1px solid #aaa',
                      borderRadius: 18,
                      display: 'flex',
                      alignItems: 'center',
                      justifyContent: 'center',
                      background: val === deleteNum ? '#ffccc7' : '#fff',
                      fontWeight: val === deleteNum ? 'bold' : 'normal',
                    }}
                  >
                    {val === null ? '' : val}
                  </div>
                ))}
              </div>
            ))}
          </div>
        )}
      </Card>

      <Typography.Text type="secondary">
        提示：点击"删除节点"后可以查看详细的删除过程步骤。
      </Typography.Text>
    </Space>
  );
}
